package com.lw.leetcode.other.c;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 829. 连续整数求和
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/3 20:30
 */
public class ConsecutiveNumbersSum {

    public static void main(String[] args) {
        ConsecutiveNumbersSum test = new ConsecutiveNumbersSum();
        int[] arr1 = {9, 15, 45, 1000000000, 933320757, 1155, 2310, 37, 1, 15, 5, 100000007, 45};
        int[] arr2 = {3, 4, 6, 10, 16, 16, 16, 2, 1, 4, 2, 2, 6};
        for (int i = 0; i < arr1.length; i++) {
            int v = test.consecutiveNumbersSum(arr1[i]);
            if (v != arr2[i]) {
                System.out.println(arr1[i] + "  " + v + "  " + arr2[i]);
            }
        }
        System.out.println("ok");
    }


    public int consecutiveNumbersSum(int n) {
        if (n == 1) {
            return 1;
        }
        List<Integer> list = getList(n);
        List<Integer> all = new ArrayList<>();
        all.add(1);
        int count = 1;
        if ((n & 1) == 1) {
            count++;
        }
        Set<Integer> set = new HashSet<>();
        for (int s : list) {
            int size = all.size();
            for (int j = 0; j < size; j++) {
                int i = all.get(j) * s;
                if (set.contains(i)) {
                    continue;
                }
                set.add(i);
                all.add(i);
                if (n % i == 0) {
                    int v = n / i;
                    if ((i & 1) == 1 && v - (i >> 1) > 0) {
                        count++;
                    }
                    if ((v & 1) == 1 && v / 2 - i + 1 > 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private List<Integer> getList(int n) {
        int item = 2;
        List<Integer> list = new ArrayList<>();
        int end = (int) Math.pow(n, 0.5);
        while (item <= end && n > 1) {
            if (n % item == 0) {
                n /= item;
                list.add(item);
                item = 2;
            } else {
                item++;
            }
        }
        if (n > end) {
            list.add(n);
        }
        return list;
    }

}
